/*
 * Copyright (c) 2012, Metron, Inc.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of Metron, Inc. nor the
 *       names of its contributors may be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL METRON, INC. BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package com.metsci.glimpse.util.primitives.algorithms;

import com.metsci.glimpse.util.primitives.algorithms.GenericSorting.Comparator;
import com.metsci.glimpse.util.primitives.algorithms.GenericSorting.Swapper;

/**
 * @author osborn
 */
public class Sorting
{
    public static boolean isSorted( long[] x )
    {
        return isSorted( x, 0, x.length );
    }

    public static boolean isSorted( long[] x, int fromIndex, int toIndex )
    {
        for( int i = fromIndex; i < toIndex-1; i++ )
            if( x[i] > x[i+1] )
                return false;

        return true;
    }

    public static void mergesort( final long[] x, final int[] aux, int fromIndex, int toIndex )
    {
         final Swapper swap = new Swapper() {

             long xTemp;
             int auxTemp;

             public void swap(int a, int b) {

                 xTemp = x[a];
                 x[a] = x[b];
                 x[b] = xTemp;

                 auxTemp = aux[a];
                 aux[a] = aux[b];
                 aux[b] = auxTemp;

             }

             protected void vecswap(int a0, int b0, int n) {

                 for (int i = 0, a = a0, b = b0; i < n; i++, a++, b++)
                 {
                     xTemp = x[a];
                     x[a] = x[b];
                     x[b] = xTemp;
                 }

                 for (int i = 0, a = a0, b = b0; i < n; i++, a++, b++)
                 {
                     auxTemp = aux[a];
                     aux[a] = aux[b];
                     aux[b] = auxTemp;
                 }

             }
         };

         final Comparator comp = new Comparator()
         {
             public int compare(int a, int b)
             {
                 return x[a] == x[b] ? 0 : (x[a] < x[b] ? -1 : 1);
             }
         };

         GenericSorting.mergesort(fromIndex, toIndex, comp, swap);
    }

    public static void quicksort( final long[] x, final int[] aux, int fromIndex, int toIndex )
    {
         final Swapper s = new Swapper() {

             long xTemp;
             int auxTemp;

             public void swap(int a, int b) {

                 xTemp = x[a];
                 x[a] = x[b];
                 x[b] = xTemp;

                 auxTemp = aux[a];
                 aux[a] = aux[b];
                 aux[b] = auxTemp;

             }

             protected void vecswap(int a0, int b0, int n) {

                 for (int i = 0, a = a0, b = b0; i < n; i++, a++, b++)
                 {
                     xTemp = x[a];
                     x[a] = x[b];
                     x[b] = xTemp;
                 }

                 for (int i = 0, a = a0, b = b0; i < n; i++, a++, b++)
                 {
                     auxTemp = aux[a];
                     aux[a] = aux[b];
                     aux[b] = auxTemp;
                 }

             }
         };

         final Comparator c = new Comparator()
         {
             public int compare( int a, int b )
             {
                 return x[a] == x[b] ? 0 : (x[a] < x[b] ? -1 : 1);
             }
         };

         GenericSorting.quicksort(fromIndex, toIndex, c, s);
    }
}
